SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Multinomial theorem</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Multinomial theorem</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>In <a href="Mathematics" title="Mathematics">mathematics</a>, the <b>multinomial theorem</b> describes how to expand a <a href="Power_(mathematics)" class="mw-redirect" title="Power (mathematics)">power</a> of a <a href="Summation" title="Summation">sum</a> in terms of powers of the terms in that sum. It is the <a href="Generalization" title="Generalization">generalization</a> of the <a href="Binomial_theorem" title="Binomial theorem">binomial theorem</a> from <a href="Binomial_(polynomial)" title="Binomial (polynomial)">binomials</a> to <a href="Polynomial" title="Polynomial">multinomials</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Theorem">Theorem</h2></div>

<p>For any positive integer <span class="texhtml mvar" style="font-style:italic;">m</span> and any non-negative integer <span class="texhtml mvar" style="font-style:italic;">n</span>, the multinomial theorem describes how a sum with <span class="texhtml mvar" style="font-style:italic;">m</span> terms expands when raised to the <span class="texhtml mvar" style="font-style:italic;">n</span>th power:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</munder>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1}+x_{2}+\cdots +x_{m})^{n}=\sum _{\begin{array}{c}k_{1}+k_{2}+\cdots +k_{m}=n\\k_{1},k_{2},\cdots ,k_{m}\geq 0\end{array}}{n \choose k_{1},k_{2},\ldots ,k_{m}}x_{1}^{k_{1}}\cdot x_{2}^{k_{2}}\cdots x_{m}^{k_{m}}}</annotation>

</semantics>

</math></span></span>

where

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}}</annotation>

</semantics>

</math></span></span>

is a <b>multinomial coefficient</b>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The sum is taken over all combinations of <a href="Nonnegative" class="mw-redirect" title="Nonnegative">nonnegative</a> <a href="Integer" title="Integer">integer</a> indices <span class="texhtml"><i>k</i><sub>1</sub></span> through <span class="texhtml mvar" style="font-style:italic;">k<sub>m</sub></span> such that the sum of all <span class="texhtml mvar" style="font-style:italic;">k<sub>i</sub></span> is <span class="texhtml mvar" style="font-style:italic;">n</span>. That is, for each term in the expansion, the exponents of the <span class="texhtml mvar" style="font-style:italic;">x<sub>i</sub></span> must add up to <span class="texhtml mvar" style="font-style:italic;">n</span>.<sup id="cite_ref-EC1_2-0" class="reference"><a href="#cite_note-EC1-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>a<span class="cite-bracket">]</span></a></sup>

</p><p>In the case <span class="texhtml"><i>m</i> = 2</span>, this statement reduces to that of the <a href="Binomial_theorem" title="Binomial theorem">binomial theorem</a>.<sup id="cite_ref-EC1_2-1" class="reference"><a href="#cite_note-EC1-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Example">Example</h3></div>

<p>The third power of the trinomial <span class="texhtml"><i>a</i> + <i>b</i> + <i>c</i></span> is given by

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a+b+c)^{3}=a^{3}+b^{3}+c^{3}+3a^{2}b+3a^{2}c+3b^{2}a+3b^{2}c+3c^{2}a+3c^{2}b+6abc.}</annotation>

</semantics>

</math></span></span>

This can be computed by hand using the <a href="Distributive_property" title="Distributive property">distributive property</a> of multiplication over addition and combining <a href="Like_terms" title="Like terms">like terms</a>, but it can also be done (perhaps more easily) with the multinomial theorem. It is possible to "read off" the multinomial coefficients from the terms by using the multinomial coefficient formula. For example, the term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{2}b^{0}c^{1}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{2}b^{0}c^{1}}</annotation>

</semantics>

</math></span><img src="./7b38c1eec429e51d7dc1780567be2ef00a7ac1f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.397ex; height:2.676ex;" alt="{\displaystyle a^{2}b^{0}c^{1}}" loading="lazy"></span> has coefficient <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {3 \choose 2,0,1}={\frac {3!}{2!\cdot 0!\cdot 1!}}={\frac {6}{2\cdot 1\cdot 1}}=3}">

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {3 \choose 2,0,1}={\frac {3!}{2!\cdot 0!\cdot 1!}}={\frac {6}{2\cdot 1\cdot 1}}=3}</annotation>

</semantics>

</math></span><img src="./c0840d7ec3fa993e6f325c10612f1767cece611d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:36.738ex; height:6.176ex;" alt="{\displaystyle {3 \choose 2,0,1}={\frac {3!}{2!\cdot 0!\cdot 1!}}={\frac {6}{2\cdot 1\cdot 1}}=3}" loading="lazy"></span>, the term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{1}b^{1}c^{1}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{1}b^{1}c^{1}}</annotation>

</semantics>

</math></span><img src="./ab584a87fd1fff9a854b37db72fe3690a9d86cf8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.397ex; height:2.676ex;" alt="{\displaystyle a^{1}b^{1}c^{1}}" loading="lazy"></span> has coefficient <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {3 \choose 1,1,1}={\frac {3!}{1!\cdot 1!\cdot 1!}}={\frac {6}{1\cdot 1\cdot 1}}=6}">

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {3 \choose 1,1,1}={\frac {3!}{1!\cdot 1!\cdot 1!}}={\frac {6}{1\cdot 1\cdot 1}}=6}</annotation>

</semantics>

</math></span><img src="./578accc466b59d869bddc3edefaed1fdd3c8f35b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:36.738ex; height:6.176ex;" alt="{\displaystyle {3 \choose 1,1,1}={\frac {3!}{1!\cdot 1!\cdot 1!}}={\frac {6}{1\cdot 1\cdot 1}}=6}" loading="lazy"></span>, and so on.

</p>

<div class="mw-heading mw-heading3"><h3 id="Alternate_expression">Alternate expression</h3></div>

<p>The statement of the theorem can be written concisely using <a href="Multiindices" class="mw-redirect" title="Multiindices">multiindices</a>:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</munder>

<mrow>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1}+\cdots +x_{m})^{n}=\sum _{|\alpha |=n}{n \choose \alpha }x^{\alpha }}</annotation>

</semantics>

</math></span><img src="./ecc6ec7c98dbbb25a3f874ee1118e2892a128822.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:32.06ex; height:7.176ex;" alt="{\displaystyle (x_{1}+\cdots +x_{m})^{n}=\sum _{|\alpha |=n}{n \choose \alpha }x^{\alpha }}" loading="lazy"></span></dd></dl>

<p>where

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha =(\alpha _{1},\alpha _{2},\dots ,\alpha _{m})}</annotation>

</semantics>

</math></span><img src="./99a6126660396526ff1c7cc0e1d3b838a724a0c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.854ex; height:2.843ex;" alt="{\displaystyle \alpha =(\alpha _{1},\alpha _{2},\dots ,\alpha _{m})}" loading="lazy"></span></dd></dl>

<p>and

</p>

<msup>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{\alpha }=x_{1}^{\alpha _{1}}x_{2}^{\alpha _{2}}\cdots x_{m}^{\alpha _{m}}}</annotation>

</semantics>

</math></span><img src="./e3c55634a7a0607e1ba144f45b0e609ba860bc83.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:20.05ex; height:3.176ex;" alt="{\displaystyle x^{\alpha }=x_{1}^{\alpha _{1}}x_{2}^{\alpha _{2}}\cdots x_{m}^{\alpha _{m}}}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Proof">Proof</h3></div>

<p>This proof of the multinomial theorem uses the <a href="Binomial_theorem" title="Binomial theorem">binomial theorem</a> and <a href="Mathematical_induction" title="Mathematical induction">induction</a> on <span class="texhtml mvar" style="font-style:italic;">m</span>.

</p><p>First, for <span class="texhtml"><i>m</i> = 1</span>, both sides equal <span class="texhtml"><i>x</i><sub>1</sub><sup><i>n</i></sup></span> since there is only one term <span class="texhtml"><i>k</i><sub>1</sub> = <i>n</i></span> in the sum. For the induction step, suppose the multinomial theorem holds for <span class="texhtml mvar" style="font-style:italic;">m</span>. Then

</p>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&(x_{1}+x_{2}+\cdots +x_{m}+x_{m+1})^{n}=(x_{1}+x_{2}+\cdots +(x_{m}+x_{m+1}))^{n}\\[6pt]={}&\sum _{k_{1}+k_{2}+\cdots +k_{m-1}+K=n}{n \choose k_{1},k_{2},\ldots ,k_{m-1},K}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m-1}^{k_{m-1}}(x_{m}+x_{m+1})^{K}\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./1adc5f8add6e0ee01e9fc422b22e5d75ac722cc7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.171ex; width:74.178ex; height:11.509ex;" alt="{\displaystyle {\begin{aligned}&(x_{1}+x_{2}+\cdots +x_{m}+x_{m+1})^{n}=(x_{1}+x_{2}+\cdots +(x_{m}+x_{m+1}))^{n}\\[6pt]={}&\sum _{k_{1}+k_{2}+\cdots +k_{m-1}+K=n}{n \choose k_{1},k_{2},\ldots ,k_{m-1},K}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m-1}^{k_{m-1}}(x_{m}+x_{m+1})^{K}\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>by the induction hypothesis. Applying the binomial theorem to the last factor,

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle =\sum _{k_{1}+k_{2}+\cdots +k_{m-1}+K=n}{n \choose k_{1},k_{2},\ldots ,k_{m-1},K}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m-1}^{k_{m-1}}\sum _{k_{m}+k_{m+1}=K}{K \choose k_{m},k_{m+1}}x_{m}^{k_{m}}x_{m+1}^{k_{m+1}}}</annotation>

</semantics>

</math></span><img src="./700d5ffcfe1326131b0a75b1c16b5bfa5a10410f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:91.01ex; height:7.176ex;" alt="{\displaystyle =\sum _{k_{1}+k_{2}+\cdots +k_{m-1}+K=n}{n \choose k_{1},k_{2},\ldots ,k_{m-1},K}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m-1}^{k_{m-1}}\sum _{k_{m}+k_{m+1}=K}{K \choose k_{m},k_{m+1}}x_{m}^{k_{m}}x_{m+1}^{k_{m+1}}}" loading="lazy"></span></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle =\sum _{k_{1}+k_{2}+\cdots +k_{m-1}+k_{m}+k_{m+1}=n}{n \choose k_{1},k_{2},\ldots ,k_{m-1},k_{m},k_{m+1}}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m-1}^{k_{m-1}}x_{m}^{k_{m}}x_{m+1}^{k_{m+1}}}</annotation>

</semantics>

</math></span><img src="./22353333d5fb55b5b01c209c7aefafe1f630bbe6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:80.548ex; height:7.176ex;" alt="{\displaystyle =\sum _{k_{1}+k_{2}+\cdots +k_{m-1}+k_{m}+k_{m+1}=n}{n \choose k_{1},k_{2},\ldots ,k_{m-1},k_{m},k_{m+1}}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m-1}^{k_{m-1}}x_{m}^{k_{m}}x_{m+1}^{k_{m+1}}}" loading="lazy"></span></dd></dl>

<p>which completes the induction. The last step follows because

</p>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m-1},K}{K \choose k_{m},k_{m+1}}={n \choose k_{1},k_{2},\ldots ,k_{m-1},k_{m},k_{m+1}},}</annotation>

</semantics>

</math></span><img src="./c0b2f4b3a147691c33e91e95242ce7323ed2232d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:67.416ex; height:6.176ex;" alt="{\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m-1},K}{K \choose k_{m},k_{m+1}}={n \choose k_{1},k_{2},\ldots ,k_{m-1},k_{m},k_{m+1}},}" loading="lazy"></span></dd></dl>

<p>as can easily be seen by writing the three coefficients using factorials as follows:

</p>

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {n!}{k_{1}!k_{2}!\cdots k_{m-1}!K!}}{\frac {K!}{k_{m}!k_{m+1}!}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{m+1}!}}.}</annotation>

</semantics>

</math></span><img src="./3cfe00db0b498412d198e56b4af8b4d2d8c1c73a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:48.045ex; height:6.009ex;" alt="{\displaystyle {\frac {n!}{k_{1}!k_{2}!\cdots k_{m-1}!K!}}{\frac {K!}{k_{m}!k_{m+1}!}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{m+1}!}}.}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Multinomial_coefficients">Multinomial coefficients</h2></div>

<p>The numbers

</p>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}}</annotation>

</semantics>

</math></span><img src="./7a96fa79c67c62c56f09607af0e0ba24a2d56782.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:17.051ex; height:6.176ex;" alt="{\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}}" loading="lazy"></span></dd></dl>

<p>appearing in the theorem are the <a href="Binomial_coefficient#Generalization_to_multinomials" title="Binomial coefficient">multinomial coefficients</a>. They can be expressed in numerous ways, including as a product of <a href="Binomial_coefficient" title="Binomial coefficient">binomial coefficients</a> or of <a href="Factorial" title="Factorial">factorials</a>:

</p>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}={k_{1} \choose k_{1}}{k_{1}+k_{2} \choose k_{2}}\cdots {k_{1}+k_{2}+\cdots +k_{m} \choose k_{m}}}</annotation>

</semantics>

</math></span><img src="./0618a64f7b9624fd8ae0df67100096d16cf016c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:79.385ex; height:6.176ex;" alt="{\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}={k_{1} \choose k_{1}}{k_{1}+k_{2} \choose k_{2}}\cdots {k_{1}+k_{2}+\cdots +k_{m} \choose k_{m}}}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Sum_of_all_multinomial_coefficients">Sum of all multinomial coefficients</h3></div>

<p>The substitution of <span class="texhtml"><i>x<sub>i</sub></i> = 1</span> for all <span class="texhtml mvar" style="font-style:italic;">i</span> into the multinomial theorem

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{k_{1}+k_{2}+\cdots +k_{m}=n}{n \choose k_{1},k_{2},\ldots ,k_{m}}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m}^{k_{m}}=(x_{1}+x_{2}+\cdots +x_{m})^{n}}</annotation>

</semantics>

</math></span><img src="./61d180aaa841eb80841959a48ba78a0b2068a467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:69.926ex; height:7.009ex;" alt="{\displaystyle \sum _{k_{1}+k_{2}+\cdots +k_{m}=n}{n \choose k_{1},k_{2},\ldots ,k_{m}}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m}^{k_{m}}=(x_{1}+x_{2}+\cdots +x_{m})^{n}}" loading="lazy"></span></dd></dl>

<p>gives immediately that

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{k_{1}+k_{2}+\cdots +k_{m}=n}{n \choose k_{1},k_{2},\ldots ,k_{m}}=m^{n}.}</annotation>

</semantics>

</math></span><img src="./2099df0e9c29db97d9e588ea5ef39a5afcda2178.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:38.036ex; height:7.009ex;" alt="{\displaystyle \sum _{k_{1}+k_{2}+\cdots +k_{m}=n}{n \choose k_{1},k_{2},\ldots ,k_{m}}=m^{n}.}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Number_of_multinomial_coefficients">Number of multinomial coefficients</h3></div>

<p>The number of terms in a multinomial sum, <span class="texhtml">#<sub><i>n</i>,<i>m</i></sub></span>, is equal to the number of monomials of degree <span class="texhtml mvar" style="font-style:italic;">n</span> on the variables <span class="texhtml"><i>x</i><sub>1</sub>, …, <i>x<sub>m</sub></i></span>:

</p>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \#_{n,m}={n+m-1 \choose m-1}.}</annotation>

</semantics>

</math></span><img src="./9c29ce06f15b43f19f6d3c92bee787f95ba83cd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:22.499ex; height:6.176ex;" alt="{\displaystyle \#_{n,m}={n+m-1 \choose m-1}.}" loading="lazy"></span></dd></dl>

<p>The count can be performed easily using the method of <a href="Stars_and_bars_(combinatorics)" title="Stars and bars (combinatorics)">stars and bars</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Valuation_of_multinomial_coefficients">Valuation of multinomial coefficients</h3></div>

<p>The largest power of a prime <span class="texhtml mvar" style="font-style:italic;">p</span> that divides a multinomial coefficient may be computed using a generalization of <a href="Kummer's_theorem" title="Kummer's theorem">Kummer's theorem</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Asymptotics">Asymptotics</h3></div>

<p>By <a href="Stirling's_approximation" title="Stirling's approximation">Stirling's approximation</a>, or equivalently the <a href="Gamma_function" title="Gamma function">log-gamma function</a>'s <a href="Asymptotic_expansion" title="Asymptotic expansion">asymptotic expansion</a>, <span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log {\binom {kn}{n,n,\cdots ,n}}=kn\log(k)+{\frac {1}{2}}\left(\log(k)-(k-1)\log(2\pi n)\right)-{\frac {k^{2}-1}{12kn}}+{\frac {k^{4}-1}{360k^{3}n^{3}}}-{\frac {k^{6}-1}{1260k^{5}n^{5}}}+O\left({\frac {1}{n^{6}}}\right)}">

<mrow>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log {\binom {kn}{n,n,\cdots ,n}}=kn\log(k)+{\frac {1}{2}}\left(\log(k)-(k-1)\log(2\pi n)\right)-{\frac {k^{2}-1}{12kn}}+{\frac {k^{4}-1}{360k^{3}n^{3}}}-{\frac {k^{6}-1}{1260k^{5}n^{5}}}+O\left({\frac {1}{n^{6}}}\right)}</annotation>

</semantics>

</math></span></span>so for example,<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {2n}{n}}\sim {\frac {2^{2n}}{\sqrt {n\pi }}}}">

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<msup>

</mrow>

</msup>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\binom {2n}{n}}\sim {\frac {2^{2n}}{\sqrt {n\pi }}}}</annotation>

</semantics>

</math></span></span>

</p>

<div class="mw-heading mw-heading2"><h2 id="Interpretations">Interpretations</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Ways_to_put_objects_into_bins">Ways to put objects into bins</h3></div>

<p>The multinomial coefficients have a direct combinatorial interpretation, as the number of ways of depositing <span class="texhtml mvar" style="font-style:italic;">n</span> distinct objects into <span class="texhtml mvar" style="font-style:italic;">m</span> distinct bins, with <span class="texhtml"><i>k</i><sub>1</sub></span> objects in the first bin, <span class="texhtml"><i>k</i><sub>2</sub></span> objects in the second bin, and so on.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Number_of_ways_to_select_according_to_a_distribution">Number of ways to select according to a distribution</h3></div>

<p>In <a href="Statistical_mechanics" title="Statistical mechanics">statistical mechanics</a> and <a href="Combinatorics" title="Combinatorics">combinatorics</a>, if one has a number distribution of labels, then the multinomial coefficients naturally arise from the binomial coefficients. Given a number distribution <span class="texhtml">{<i>n<sub>i</sub></i>} </span> on a set of <span class="texhtml mvar" style="font-style:italic;">N</span> total items, <span class="texhtml mvar" style="font-style:italic;">n<sub>i</sub></span> represents the number of items to be given the label <span class="texhtml mvar" style="font-style:italic;">i</span>. (In statistical mechanics <span class="texhtml mvar" style="font-style:italic;">i</span> is the label of the energy state.)

</p><p>The number of arrangements is found by

</p>

<ul><li>Choosing <span class="texhtml"><i>n</i><sub>1</sub></span> of the total <span class="texhtml mvar" style="font-style:italic;">N</span> to be labeled 1. This can be done <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tbinom {N}{n_{1}}}}">

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tbinom {N}{n_{1}}}}</annotation>

</semantics>

</math></span><img src="./9a74a812029292cb8c9588b725f07fbb6b7aa846.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.948ex; height:3.676ex;" alt="{\displaystyle {\tbinom {N}{n_{1}}}}" loading="lazy"></span> ways.</li>

<li>From the remaining <span class="texhtml"><i>N</i> − <i>n</i><sub>1</sub></span> items choose <span class="texhtml"><i>n</i><sub>2</sub></span> to label 2. This can be done <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tbinom {N-n_{1}}{n_{2}}}}">

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tbinom {N-n_{1}}{n_{2}}}}</annotation>

</semantics>

</math></span><img src="./9afbe01319f1ed544cb8f1f1da0c6ae4d0a4da7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:6.685ex; height:3.676ex;" alt="{\displaystyle {\tbinom {N-n_{1}}{n_{2}}}}" loading="lazy"></span> ways.</li>

<li>From the remaining <span class="texhtml"><i>N</i> − <i>n</i><sub>1</sub> − <i>n</i><sub>2</sub></span> items choose <span class="texhtml"><i>n</i><sub>3</sub></span> to label 3. Again, this can be done <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tbinom {N-n_{1}-n_{2}}{n_{3}}}}">

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tbinom {N-n_{1}-n_{2}}{n_{3}}}}</annotation>

</semantics>

</math></span><img src="./16e7f668314be45486ed4c97f159bcf3ca5cf42b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:9.782ex; height:3.676ex;" alt="{\displaystyle {\tbinom {N-n_{1}-n_{2}}{n_{3}}}}" loading="lazy"></span> ways.</li></ul>

<p>Multiplying the number of choices at each step results in:

</p>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {N \choose n_{1}}{N-n_{1} \choose n_{2}}{N-n_{1}-n_{2} \choose n_{3}}\cdots ={\frac {N!}{(N-n_{1})!n_{1}!}}\cdot {\frac {(N-n_{1})!}{(N-n_{1}-n_{2})!n_{2}!}}\cdot {\frac {(N-n_{1}-n_{2})!}{(N-n_{1}-n_{2}-n_{3})!n_{3}!}}\cdots .}</annotation>

</semantics>

</math></span><img src="./25915f8c54c4a0bdacebdd92ec034cf0fb42bc67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:103.51ex; height:6.509ex;" alt="{\displaystyle {N \choose n_{1}}{N-n_{1} \choose n_{2}}{N-n_{1}-n_{2} \choose n_{3}}\cdots ={\frac {N!}{(N-n_{1})!n_{1}!}}\cdot {\frac {(N-n_{1})!}{(N-n_{1}-n_{2})!n_{2}!}}\cdot {\frac {(N-n_{1}-n_{2})!}{(N-n_{1}-n_{2}-n_{3})!n_{3}!}}\cdots .}" loading="lazy"></span></dd></dl>

<p>Cancellation results in the formula given above.

</p>

<div class="mw-heading mw-heading3"><h3 id="Number_of_unique_permutations_of_words">Number of unique permutations of words</h3></div>

<p>The multinomial coefficient

</p>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k_{1},\ldots ,k_{m}}}}</annotation>

</semantics>

</math></span><img src="./dab69caea99ffaf29a0edfbe98586dae472871db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:13.751ex; height:6.176ex;" alt="{\displaystyle {\binom {n}{k_{1},\ldots ,k_{m}}}}" loading="lazy"></span></dd></dl>

<p>is also the number of distinct ways to <a href="Permutation" title="Permutation">permute</a> a <a href="Multiset" title="Multiset">multiset</a> of <span class="texhtml mvar" style="font-style:italic;">n</span> elements, where <span class="texhtml mvar" style="font-style:italic;">k<sub>i</sub></span> is the <a href="Multiplicity_(mathematics)" title="Multiplicity (mathematics)">multiplicity</a> of each of the <span class="texhtml mvar" style="font-style:italic;">i</span>th element. For example, the number of distinct permutations of the letters of the word MISSISSIPPI, which has 1 M, 4 Is, 4 Ss, and 2 Ps, is

</p>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {11 \choose 1,4,4,2}={\frac {11!}{1!\,4!\,4!\,2!}}=34650.}</annotation>

</semantics>

</math></span><img src="./6d3ca758de254769f21464cb04f8af80ae36f4a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:33.063ex; height:6.176ex;" alt="{\displaystyle {11 \choose 1,4,4,2}={\frac {11!}{1!\,4!\,4!\,2!}}=34650.}" loading="lazy"></span></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Generalized_Pascal's_triangle">Generalized Pascal's triangle</h3></div>

<p>One can use the multinomial theorem to generalize <a href="Pascal's_triangle" title="Pascal's triangle">Pascal's triangle</a> or <a href="Pascal's_pyramid" title="Pascal's pyramid">Pascal's pyramid</a> to <a href="Pascal's_simplex" class="mw-redirect" title="Pascal's simplex">Pascal's simplex</a>. This provides a quick way to generate a lookup table for multinomial coefficients.

</p><p>A related structure is the multinomial triangle, or generalized Pascal triangle of order m, which may be constructed using the <a href="Recurrence_relation" title="Recurrence relation">recurrence relation</a>:

<msub>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

<mrow>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}_{m-1}=\sum _{i=0}^{m-1}{\binom {n-1}{k-i}}_{m-1}}</annotation>

</semantics>

</math></span></span>

from which <a href="Pascal's_rule" title="Pascal's rule">Pascal's rule</a> is recovered when <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=2}</annotation>

</semantics>

</math></span><img src="./b32de1b0dc05f6e525ad6a3e8ddeeb4321fd79e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.301ex; height:2.176ex;" alt="{\displaystyle m=2}" loading="lazy"></span>. These multinomial coefficients can be written as closed-form expressions with bounded integer compositions:

</p><p><span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{k}}_{m-1}=\sum _{\begin{array}{c}k_{0}+k_{1}+\cdots +k_{m-1}=n\\k_{1}+2k_{2}\cdots +(m-1)k_{m-1}=k\end{array}}{n \choose k_{0},k_{1},\ldots ,k_{m-1}}}">

<msub>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</msub>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</munder>

<mrow>

</mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}_{m-1}=\sum _{\begin{array}{c}k_{0}+k_{1}+\cdots +k_{m-1}=n\\k_{1}+2k_{2}\cdots +(m-1)k_{m-1}=k\end{array}}{n \choose k_{0},k_{1},\ldots ,k_{m-1}}}</annotation>

</semantics>

</math></span></span>

and without:<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> (sequence <span class="nowrap external"><a href="https://oeis.org/A008287" class="extiw external" title="oeis:A008287">A008287</a></span> in the <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>)

</p><p><span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\binom {n}{k}}_{m-1}=\sum _{i=0}^{\lfloor k/m\rfloor }(-1)^{i}{\binom {n}{i}}{\binom {n-1+k-im}{n-1}}}">

<msub>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<mrow>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\binom {n}{k}}_{m-1}=\sum _{i=0}^{\lfloor k/m\rfloor }(-1)^{i}{\binom {n}{i}}{\binom {n-1+k-im}{n-1}}}</annotation>

</semantics>

</math></span></span>

</p>

<ul><li><a href="Multinomial_distribution" title="Multinomial distribution">Multinomial distribution</a></li>

<li><a href="Stars_and_bars_(combinatorics)" title="Stars and bars (combinatorics)">Stars and bars (combinatorics)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-lower-alpha">

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">As with the <a href="Binomial_theorem" title="Binomial theorem">binomial theorem</a>, quantities of the form <span class="texhtml"><i>x</i><sup>0</sup></span> that appear are taken to equal 1, <a href="Zero_to_the_power_of_zero" title="Zero to the power of zero">even when <span class="texhtml mvar" style="font-style:italic;">x</span> equals zero</a>.</span>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAigner1997" class="citation cs2"><a href="Martin_Aigner" title="Martin Aigner">Aigner, Martin</a> (1997), <i>Combinatorial Theory</i>, Springer, p. 77</cite></span>

</li>

<li id="cite_note-EC1-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-EC1_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-EC1_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFStanley2012" class="citation cs2"><a href="Richard_P._Stanley" title="Richard P. Stanley">Stanley, Richard</a> (2012), <i>Enumerative Combinatorics</i>, vol. 1 (2 ed.), Cambridge University Press, §1.2</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFNational_Institute_of_Standards_and_Technology2010" class="citation web cs1"><a href="National_Institute_of_Standards_and_Technology" title="National Institute of Standards and Technology">National Institute of Standards and Technology</a> (May 11, 2010). <a rel="nofollow" class="external text" href="http://dlmf.nist.gov/">"NIST Digital Library of Mathematical Functions"</a>. <a rel="nofollow" class="external text" href="http://dlmf.nist.gov/26.4">Section 26.4</a><span class="reference-accessdate">. Retrieved <span class="nowrap">August 30,</span> 2010</span>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFBelbachirBouroubiKhelladi2008" class="citation cs2">Belbachir, H.; Bouroubi, S.; Khelladi, A. (2008), "Connection between ordinary multinomials, Fibonacci numbers, Bell polynomials and discrete uniform distribution", <i>Annales Mathematicae et Informaticae</i>, <b>35</b>: 24</cite>

<a rel="nofollow" class="external free" href="https://arxiv.org/abs/0708.2195">https://arxiv.org/abs/0708.2195</a>

</span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-10" href="https://en.wikipedia.org/wiki/?title=Multinomial_theorem&oldid=1299770607">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>